这是 leetcode 上算法的第一题,官方定位为简单题目,事实也是如此。题目地址
题目:给定一个整数数组,返回两个数字的返回索引,这样它们就可以添加到特定的目标。假设每个输入都只有一个结果,不会两次使用相同的元素。例如:
1 2 3 4
| Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
|
解法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| var twoSum = function(nums, target) { var d ={}; var result = []; for (var i = 0; i < nums.length; i++) { for (var j = 0; j < nums.length; j++) { if (nums[i] + nums[j] === target && i !== j) { (i < j) ? result.push(i, j) : result.push(j, i); return result; } } } return result; };
|
基本所有人都会,但是该方法算法复杂度为O(n2),运行时间过长(246ms)
解法二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| var twoSum = function(nums, target) { var d ={}; var result = []; for (var i = 0; i < nums.length; i++) { var a = target - nums[i] +''; var t = {}; d[a] = i; } for (var b = 0; b < nums.length; b++) { var c = nums[b]+''; if(d[c] !== undefined){ var x = d[c], y = nums.indexOf(nums[b]); if (x !== y){ (y < x) ? result.push(y, x) : result.push(x, y); return result; } } } return result; };
|
这种解法是用两个单独的循环,所以运行时间大大减少(116ms)。
大概思路是先做一遍遍历,将数据以’目标值减去数组中的某个值 : 该值的索引’这样类似map的方式存储在对象d中,然后再做一次遍历根据是否是新对象的属性来判断有没有解。 这个解法是我对这道题目的思考过程,中间有很多多余的操作。
解法三
1 2 3 4 5 6 7 8 9 10 11 12 13
| var twoSum = function(nums, target) { var ans = []; var exist = {}; for (var i = 0; i < nums.length; i++){ if (typeof(exist[target-nums[i]]) !== 'undefined'){ ans.push(exist[target-nums[i]]); ans.push(i); } exist[nums[i]] = i; } return ans; };
|
leetcode 上大佬的解法,运行时间(92ms),直接在一个循环中解决问题。
大致思路,就是遍历数组,在exis对象中存入’值’:’索引’的属性,使用typeof 判断是否有符合条件的属性,有的话存入ans,最后返回ans。
对于这个算法我本来想在ans.push(i)后加个 return ans,想这样不用把算法走完或许会再少点时间,但是时间反而多了一点。然后我又尝试用break,好像是减少了几ms,但是leetcode运行同样的算法时间都有变化,这个就算在误差内了。
这道题目虽然不是很难,但是加深了我对javascript基础的认知,也感受到了用javascript写算法与java这种面向对象语言的区别。